Standard Representations

A regular language is given in a standard representation if it is specified by one of:

A finite automaton (dfa or nfa).
A regular expression.
A regular grammar.

(The importance of these particular representations is simply that they are precise and unambiguous; thus, we can prove things about languages when they are expressed in a standard representation.)

Membership. If L is a language on alphabet sigma , L is in a standard representation, and w is a member of sigma *, then there is an algorithm for determining whether w L.

Proof. Build the automation and use it to test w.

Finiteness. If language L is specified by a standard representation, there is an algorithm to determine whether the set L is empty, finite, or infinite.

Proof. Build the automaton.

If there is no path from the initial state to a final state, then the language is empty (and finite).
If there is a path containing a cycle from the initial state to some final state, then the language is infinite.
If no path from the initial state to a final state contains a cycle, then the language is finite.

Equivalence. If languages L₁ and L₂ are each given in a standard representation, then there is an algorithm to determine whether the languages are identical.

Proof. Construct the language

(L₁

-L₂)

(-L₁

L₂)If this language is empty, then L₁ = L₂. (Why?)